package com.wtgroup.demo.leetcode.org_bytedance;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * 93. 复原 IP 地址 https://leetcode-cn.com/problems/restore-ip-addresses/
 *
 * @author dafei
 * @version 0.1
 * @date 2021/4/28 21:41
 */
public class Q_复原IP地址 {

    public static void main(String[] args) {
        String[] inputs = {
                // "0025525511135",
                // "25525511135",
                // "0000",
                // "1111",
                "010010",
                // "101023"
        };
        // Q_复原IP地址 exe = new Q_复原IP地址();
        Solution2 exe = new Solution2();
        for (String input : inputs) {
            List<String> res = exe.restoreIpAddresses(input);
            System.out.println(res);
        }
    }

    /**
     * My, 回溯套路解
     * 6ms
     */
    private static class Solution2 {
        public List<String> restoreIpAddresses(String s) {
            LinkedList<String> path = new LinkedList<>();
            List<String> vessel = new ArrayList<>();
            dfs(s, path, 0, 0, vessel);
            return vessel;
        }

        // 原始数据; 路径; 深度; 结果容器
        private void dfs(String src, LinkedList<String> path, int depth, int start, List<String> vessel) {
            if (depth == 4) {
                if (start == src.length()) {
                    vessel.add(String.join(".", path));
                } // else 字符多了
                return;
            }
            // 多了 或 不够, 剩余字符数/剩下的ip段数, 平均分摊超过3个, 肯定多了; 相反, 不够1个, 肯定不够
            // 考场上不要这个
            if ((src.length() - start) / (4 - depth) > 3 || (src.length() - start < 4 - depth)) {
                return;
            }

            int n = src.length();
            int first = 0;
            for (int i = start; i < n; i++) {
                // 前导0为非法
                if(i > start && first == 0) break;
                first = first * 10 + (src.charAt(i) - '0');
                if (first > 255) break;
                path.addLast(first+"");
                dfs(src, path, depth + 1, i + 1, vessel);
                path.removeLast();
            }
        }
    }

    /**
     * LC B , 99%
     */
    private class Solution {
        public List<String> restoreIpAddresses(String s) {
            int len = s.length();
            List<String> res = new ArrayList<>();
            StringBuilder S = new StringBuilder();
            int num = 0;
            backTracking(s, len, 0, S, res, num);
            return res;
        }
        public void backTracking(String s, int len, int a, StringBuilder S, List<String> res, int num){
            if(a == len && num == 3){
                res.add(new String(S));
                return;
            }
            if((len - a) / (4 - num) > 3 || 3 - num > len - a){
                return;
            }
            //
            int tens = 0, digits = 0, count = 0;
            for(int i = S.length() - 1; i >= 0; i--){
                if(S.charAt(i) != '.'){
                    if(count == 0){
                        digits = S.charAt(i) - '0';
                    }
                    else{
                        tens = S.charAt(i) - '0';
                    }
                    count++;
                } else {
                    break;
                }
            }
            int sum = tens * 100 + digits * 10 + s.charAt(a) - '0';
            if(count <= 2 && sum <= 255 && !(count == 1 && digits == 0)){
                S.append(s.charAt(a));
                backTracking(s, len, a + 1, S, res, num);
                S.deleteCharAt(S.length() - 1);
            }
            //
            if(S.length() > 0 && num < 3){
                S.append('.');
                S.append(s.charAt(a));
                backTracking(s, len, a + 1, S, res, num + 1);
                S.deleteCharAt(S.length() - 1);
                S.deleteCharAt(S.length() - 1);
            }
        }
    }


    /**
     * 回溯法
     *
     * 8ms
     * */
    public List<String> restoreIpAddresses(String s) {

        return func(s, 4);
    }

    private List<String> func(String substr, int minNum) {
        List<String> res = new ArrayList<>();
        int n = substr.length();
        if (n < minNum) { // 最少需要 minNum 但总字符数都不够, 当做空处理
            return res;
        }
        if (minNum==1) {
            if (!isValidIp(substr)) {
                return res;
            } else {
                res.add(substr);
                return res;
            }
        }


        String first = "";
        for (int firstEnd = 1; firstEnd <= n; firstEnd++) {
            first = substr.substring(0, firstEnd);
            if (!isValidIp(first)) {
                continue;
            }
            // 余下字符串, 取出切割后的结果集
            String rest = substr.substring(firstEnd);
            List<String> subres = func(rest, minNum - 1);
            for (String subre : subres) {
                res.add(first + "." + subre);
            }
        }

        return res;
    }

    // 非前导0 && <=255
    private boolean isValidIp(String s) {
        return !isLeadZero(s) && isLe255(s);
    }

    private boolean isLe255(String str) {
        if (str.length()<3) {
            return true;
        }
        if (str.length()>3) {
            return false;
        }
        return str.compareTo("255")<=0;
    }

    private boolean isLeadZero(String s) {
        if (s.length()<2) {
            return false;
        }
        return s.startsWith("0");
    }

}
